


// 
/**
 * https://leetcode.cn/problems/longest-palindromic-substring/
 * 最长回文字符串，有4种解法
暴力枚举法：时间复杂度为O(n^3)，空间复杂度为O(1)。

中心扩展法：时间复杂度为O(n^2)，空间复杂度为O(1)。

Manacher算法：时间复杂度为O(n)，空间复杂度为O(n)。

动态规划：时间复杂度为O(n^2)，空间复杂度为O(n^2)。
因此，Manacher算法是最优的，时间复杂度和空间复杂度都是线性的。

 * 
 * 重点1:连续子串,2:结果只返回最长的字符串，那么我们只要记录位置和长度，最后截取字符串即可

 */

/**
 * 暴力解法
 * 解题思路：从大到小的循环所有子字符串，只要找到比当前字符串大的，则直接返回
 * O(n*n* log n)
 * 260ms
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res=''
    for (let i = 0; i < s.length; i++) {
        for (let j = s.length; j >i; j--) {
            const length=j-i;
            // 小于当前的回文长度的都不需要检查
            if(length<=res.length)break;
            const element = s.substring(i,j)
            // 是否回文，当前长度是否大于之前的回文字符串
            if(isPalindrome(element) && length>res.length){
                res=element;
            }
            // 因为从大到小，如果当前结果等于字符串的总长度，那么就直接返回
            if(res.length==s.length){
                return res;
            }
            console.log(i,j,element,length,res)
        }
        
    }
    return res;
};

var isPalindrome = function(x) {
    let left=0;
    let right=x.length-1;
    
   while(left<right){
    
        if(x[left]!==x[right]){
            return false;
        }
        left++;
        right--;
   }
   
    return true;
};



// 递归超出时间限制 O(n^2)
var longestPalindrome1 = function(s) {
    let max='';
    function long(s){
        console.log(s)
        if(isPalindrome(s) && s.length>max.length){
            max=s;
            console.log('isPalindrome',s,max)
            return s;
        }
        if(s.length<=1){
            return s;
        }
        console.log(max.length,s.length)
        // 如果当前回文长度大于等于当前字符串，就
        if(max.length<s.length-1){
            long(s.substring(0,s.length-1));
            long(s.substring(1,s.length));
        }
            return max;
        
    }
    return long(s);
    
};

// 动态规划 556 ms O(n^2)
// 当前的a元素和 b子串是否相同，如果相同，则判断中间的子串是否相同（arr[j+1][i-1]）
// 公式等于 s[j]===s[i]&&arr[j+1][i-1]!==false
//  0 ,1, 2, 3, 4
// 0[true, false, false, false]
// 1[null, true, false, true]
// 2[null, null, true, false]
// 3[null, null, null, true]
var longestPalindrome2= function(s) {
    let arr=[]
    for (let index = 0; index < s.length; index++) {
        arr[index]=new Array(s.length).fill(null);
       arr[index][index]=true;
    }
    let max={start:0,len:1};
    // i=结束位置，j=开始位置
   for(let i=1;i<s.length;i++){
        for (let j = 0; j < i; j++) {
            //const element = array[j];
            console.log(arr,j,i,s[j],s[i],arr[j+1][i-1])
           
            if(s[j]===s[i]&&arr[j+1][i-1]!==false){
                arr[j][i]=true;
                const len=i-j+1;
                console.log(len)
                // 保存最长值
                if(len>max.len){
                    max.start=j;
                    max.len=len;
                }
            }else{
                arr[j][i]=false;
            }
        }
   }
  
    return s.substring(max.start,max.start+max.len)
    
};


// console.log('res',longestPalindrome2('cbab'))






// string longestPalindrome(string s){
//     if(s.empty()||s.size()<2){
//         return s;
//     }
//     int maxStrLen=0;
//     int maxStrStart=0;
//     for(int i=0;i<s.size();i++){
//         //注意是开区间
//         int left=i-1;
//         int right=i+1;
//         int currentLen=1;
//         //出现连续重复字符，比如cccc
//         //判断两大种情况
//         while(left>=0&&s[left]==s[i]){
//             left--;
//             currentLen++;
//         }
//         while(right<s.size()&&s[right]==s[i]){
//             right++;
//             currentLen++;
//         }
//         while(left>=0&&right<s.size()&&s[left]==s[right]){
//             left--;
//             right++;
//             currentLen+=2;
//         }
//         if(currentLen>maxStrLen){
//             maxStrLen=currentLen;
//             maxStrStart=left+1;//找到最左边界下标
//         }


//     }
//     return s.substr(maxStrStart,maxStrStart+maxStrLen);
// }
/**
 * o(n^3)
 * @param {*} s 
 * @returns 
 */
var longestPalindrome3= function(s) {
    let res='';
    for (let i = 0; i < s.length; i++) {
        for(let j=s.length;j>=0;j--){
            // 6588 ms=>400ms
            if(res.length>j-i){
                break;
            }
            
            const substr=s.substring(i,j);
            console.log(substr,res.length,j-i)
            
            if(isPalindrome(substr) && substr.length>=res.length){
                res=substr
            }
            
        }
        
    }
    return res;
}


// console.log('res',isPalindrome('cc'))
console.log('res',longestPalindrome3('"abccccdd"'))